package leetcode_ago.sort;

import java.util.NoSuchElementException;
import java.util.Random;

/**
 * @author 美女
 * @date 2022/03/20 17:32
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 **/
public class Num251_FindKLargest {
    private  Random random=new Random();
    public  int findKthLargest(int[] nums, int k) {
        //利用快排分区函数，在分区时找到分区后元素索引与nums.length-k索引相同时的值，这个值就是要找的值
        //返回最大元素
        //nums.length-k:倒数第k个位置；第k个最大元素就是排序后倒数第nums.length-k的元素
        if(k>nums.length){
            throw new NoSuchElementException("illegal k,error");
        }
        return quickSortSelect(nums,0,nums.length-1,nums.length-k);
    }
    //选择是否进行排序，==情况不用排序了直接返回值即可，此题主要是求值
    private  int quickSortSelect(int[] nums, int l, int r, int index) {
        //如果index和返回的分界点的索引相同，就不用继续快排了
        int p=partition(nums,l,r);//返回分界点索引
        if(p==index){
            return nums[p];
        }
        //排序好的分区点索引不等于倒数第k个索引index
        //分区点下标<index，递归右区间，>index递归左区间
        return p<index?quickSortSelect(nums,p+1,r,index):quickSortSelect(nums,l,p-1,index);
    }
    //nums[l...r]进行排序
    private  int partition(int[] nums, int l, int r) {
        int randomIndex=random.nextInt(r-l+1)+l;
        swap(nums,l,randomIndex);
        int v=nums[l];
        //nums[l+1...j]<v
        //nums[j+1...i)>=v
        int j=l;
        //i时当前正在遍历元素
        for (int i = l+1; i <= r ; i++) {
            if(nums[i]<v){
                swap(nums,i,j+1);
                j++;
            }//else只需要i++,条件里已经写了
        }
        //循环完毕一次分区就分好了，交换l与j索引位置元素（j位置是<v的最后一个元素）
        swap(nums,l,j);
        return j;
    }

    private  void swap(int[] nums, int i, int j) {
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }

//    public static void main(String[] args) {
//        int[] str={3};
//        int a=findKthLargest(str,2);
//        System.out.println(a);
//    }
}
